﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace PojProject.Others
{
    public class Dijkstra
    {
        private List<int> totalNode;
        public List<int> TotalNode
        {
            get
            {
                if (totalNode == null)
                {
                    totalNode = new List<int>();
                    totalNode = edges.Select(x => x.StartNodeId).
                        Union(edges.Select(x => x.EndNodeId)).Distinct().OrderBy(x => x).ToList();
                }

                return totalNode;
            }
        }

        /// <summary>
        /// 所有带权的边
        /// </summary>
        List<Edge> edges;
        /// <summary>
        /// 已经要检验的边
        /// </summary>
        Stack<int> checkPoints = new Stack<int>();
        /// <summary>
        /// 从起始点开始检查
        /// </summary>
        int currentPoint = 1;
        /// <summary>
        /// 结果，所有边每次的值（权值相加）
        /// </summary>
        List<double> pathWeights = new List<double>();
        /// <summary>
        /// 是否已经经历过的边
        /// </summary>
        List<int> hasPassNode = new List<int>();
        List<List<int>> minPathToArr = new List<List<int>>();

        // int[0,1] = 10, int[1,2] = 50, int[2,3]=20, int[3,4]=60, 
        public Dijkstra(List<Edge> edges)
        {
            this.edges = edges;
        }


        /// <summary>
        /// Summary:
        ///     Find the min path
        /// </summary>
        /// <param name="toNode">the target node that we want to arrive to from source node.</param>
        /// <returns></returns>
        public KeyValuePair<List<int>,double> Play(int toNode)
        {
            if (pathWeights.Count == 0)
            {
                InitailValue();
            }

            while (currentPoint != TotalNode.Max())
            {
                var tempWeights = pathWeights.Select((v, i) => new { item = v, index = i }).Where(x => !checkPoints.Contains(x.index + 2)).Select(x => x.item);
                var minNode = pathWeights.IndexOf(tempWeights.Min()) + 2;
                checkPoints.Push(minNode);
                currentPoint = minNode;

                UpdatePathWeights(minNode);
            }

            return new KeyValuePair<List<int>, double>(minPathToArr[toNode - 2], pathWeights[toNode - 2]);
        }

        private void UpdatePathWeights(int minNode)
        {
            for (int i = 0; i < pathWeights.Count; i++)
            {
                var tempWeight = edges.FirstOrDefault(x => x.StartNodeId == minNode && x.EndNodeId == i + 2);
                var tempValue = tempWeight == null ? double.MaxValue : tempWeight.WeightValue;

                if (currentPoint > 1)
                {
                    if (tempValue + pathWeights[currentPoint - 2] < pathWeights[i])
                    {
                        minPathToArr[i].Clear(); // 去掉之前的路径 
                        // eg 1->4 (30) 4->3 (20) ==> 1->3 (30 + 20)
                        minPathToArr[i].AddRange(minPathToArr[currentPoint - 2]); // 比如说这里我们直接加上 1->4
                        minPathToArr[i].Insert(minPathToArr[i].Count, tempWeight.EndNodeId); // 这里我们在之前得到了 4->3 所以我们只要把 结束3 带入即可。
                    }

                    pathWeights[i] = Math.Min(tempValue + pathWeights[currentPoint - 2], pathWeights[i]);
                }
            }
        }

        private void InitailValue()
        {
            var sourceNode = TotalNode.FirstOrDefault();
            var sourceWithOutFirst = totalNode.Skip(1);

            int i = 2;
            foreach (var node in sourceWithOutFirst)
            {
                var weightValue = edges.FirstOrDefault(x => x.StartNodeId == sourceNode && x.EndNodeId == node);

                if (weightValue != null)
                {
                    pathWeights.Add(weightValue.WeightValue);
                }
                else
                {
                    pathWeights.Add(double.MaxValue);
                }

                minPathToArr.Add(new List<int> { 1, i });
                i++;
            }

            checkPoints.Push(sourceNode);
            currentPoint = sourceNode;
        }


    }

    /// <summary>
    /// Summary:
    ///     The property that indicate the infos of path and node
    /// </summary>
    public class Edge
    {
        public int StartNodeId { get; set; }
        public int EndNodeId { get; set; }

        public int WeightValue { get; set; }
    }
}
